package graph;

import list.Queue;

/**
 * description:
 * author:张腾
 * date:2021-04-13
 */
/**
 * 广度优先搜素
 * 当一个节点有兄弟节点和子节点时，优先搜索兄弟节点
 * 参考 树的层序遍历
 */
public class BreadthFirstSearch {
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点和s顶点相通
    private int count;
    //用来存储待搜索邻接表的点
    private Queue<Integer> waitSearch;

    //构造广度优先搜索对象，使用宽搜找出G图中s顶点的所有相邻顶点
    public BreadthFirstSearch(Graph G,int s){

        this.marked = new boolean[G.V()];
        this.count = 0;
        this.waitSearch = new Queue<Integer>();

        bfs(G,s);
    }

    //使用宽搜找出G图中v顶点的所有相通顶点

    private void bfs(Graph g, int v) {
        waitSearch.enqueue(v);
        while (!waitSearch.isEmpty()) {
            Integer w = waitSearch.dequeue();
            if (marked(w)) {
                continue;
            }
            marked[w] = true;
            count++;
            for (Integer s : g.adj(w)) {
                waitSearch.enqueue(s);
            }
        }
    }

    //判断w顶点和s顶点是否相通
    public boolean marked(int w){

        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count(){

        return count;
    }
}
